package ClassicalSortingAlgorithm;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: ClassicalSortingAlgorithm
 * @Author: song
 * @CreateTime: 2022-09-19  22:28
 * @Description: TODO
 * @Version: 1.0
 */

public class shellSort {
    public static void main(String[] args) {
        int[] nums = {9,1,58,23,44,96,11,2,7,85,12};
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
        shellSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }
    public static int[] shellSort(int[] nums){
        int gap = nums.length/2;
        while (gap > 0){
            for (int i = gap; i < nums.length; i++) {
                int current = nums[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && nums[preIndex] >current){
                    nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                nums[preIndex + gap] = current;
            }
            gap /= 2;
        }
        return nums;
    }
}
